package q134_canCompleteCircuit;

public class Solution_3 {
    public static void main(String[] args) {

    }

    /**
     * 官方解法核心在于理解加油站之间的关系
     * 如果从x号加油站出发，最远到达y号加油站
     * 意味着在(x, y)的区间范围内，任何一个加油站最远也只能够到达y加油站，
     * 其实很好理解，如果能够从x号加油站出发，至少意味着x号加油量是大于路途的消耗量的，因此对于x + 1后面的加油站
     * x加油站加的油都帮助了后面的路的消耗，也就是有正向的帮助。
     * 所以x到y之间的所有加油站都不需要考虑，只需要看y + 1号加油站以及之后的加油站能够到达什么位置
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        // i < n 就是遍历所有的加油站了，i是用来计数的
        while (i < n) {
            // 用来计算剩余油量的变量
            int sumOfGas = 0, sumOfCost = 0;
            // 每次都会初始化到0的一个变量，用来计算两个加油站之间的距离
            int cnt = 0;
            // 开始循环找到i这个位置能够到达的最远加油站
            while (cnt < n) {
                // 这个j就是用来计算数组的循环所使用的，利用 % 非常有效
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                // 一旦油不够就会break，所以如果某个加油站一开始加的油少于消耗的，就直接break了
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            // 如果在上面的循环结束后，cnt达到了n，就意味着这辆车走完了全程，可以return i
            if (cnt == n) {
                return i;
            } else {
                // 否则就是没能走完全程，把i放到i + cnt + 1的位置继续尝试
                i = i + cnt + 1;
            }
        }
        return -1;
    }

}
